1. Field of the Invention
The present invention is related to the encoding and decoding of error correction codes in data communications and/or data storage systems, and in particular, to encoding and syndrome computation for cyclic codes.
2. Description of the Related Art
Error correction coding is often used in data communication systems and data storage systems to protect the integrity of the data transmitted over the communication channel or stored in the storage medium against data-corrupting conditions such as channel noise and storage medium defects, etc. Cyclic codes are a class of error correction codes which is often used due to their algebraic properties which lead to very practical implementations of the encoding and decoding algorithms.
FIG. 1 illustrates a generalized error correction coding scheme in a host system (101). In transmission to the channel/medium, the data generated by the data source (102) are encoded by the encoder (104). The encoded data are then sent to the physical interface (106) which manipulates the encoded data into a format suitable for transmission over the channel/medium (107). The physical interface (106) varies tremendously among different systems according to the specific characteristics of the channel/medium. In reading from the channel/medium, the physical interface (106) reads data potentially with errors from the channel/medium (107) and restores the encoded data format. The read encoded data is then sent to the decoder (105) where data in the original format from the data source (102) is recovered and sent to the data destination (103). The present invention focuses on the encoder (104) and decoder (105).
For an (n, k) cyclic code, encoding maps a sequence of k message symbols from the data source into another sequence of n symbols, commonly referred to as a “codeword”, where n>k. Encoding methods are generally divided into two categories, namely the systematic and the non-systematic encoding. With systematic encoding, the message appears in the codeword itself, occupying the first k symbols of the codeword. With non-systematic encoding, the message does not necessarily appear in its corresponding codeword. The present invention focuses on systematic encoding.
As illustrated in FIG. 2, a widely known prior-art systematic cyclic code encoder is a feedback shift register (FSR) which calculates the parity and appends the parity after the message to form a codeword. The k message symbols are input (205), one symbol per cycle, while the “output-enable” signal (206) equals zero which causes the multiplexer (204) to pass each message symbol into the adder (202) and simultaneously to the output (203) as a codeword symbol. After all message symbols have been input, the n−k parity symbols are obtained and stored in the registers (201). The output-enable signal is then changed to one, which causes the multiplexer to pass the parity symbols to the output (203), one symbol per cycle. As a consequence, the systematically encoded codeword appears at output, one symbol per cycle.
Since the prior-art encoder processes one symbol per cycle, it is required that the clock rate of the FSR be the same as the rate at which symbols are input to the FSR. However, some host systems may have a symbol transfer rate higher than the achievable or desirable clock rate of the FSR. For example, in a system using a flash memory having an 8-bit interface as data storage where the host transfers data to the flash memory at a rate of one byte per 20 nanosecond, i.e. 50 mega bytes per second, or 400 mega bits per second, if the error correction code selected for this flash memory is a binary BCH code where the symbol size is one bit, then the FSR needs to be clocked at 400 MHz to accommodate the flash memory transfer rate. In many semiconductor designs, such a high clock rate is undesirable or unachievable.
Further, the symbol transfer rate of the host system may vary across time or different applications. For example, if the system in the above example can be configured to employ a flash memory having a 16-bit interface, then the data transfer rate is twice that of a flash memory having an 8-bit interface, even if the transfer cycle rate remains constant. If the prior-art encoder is used, then the clock rate of the FSR has to be changed according to the data transfer rate of the system. Since it adds to the system complexity to provide varying clock rates, it is not desirable to use the prior-art encoder in a system with varying data transfer rate.
Further, the error characteristics of the channel/medium may also vary across time or different applications, and thus may require different error correction codes to achieve different levels of data integrity. Since the prior-art encoder is fixed for a particular code, a system using the prior-art encoder is prohibited from employing a channel/medium which requires a different error correcting capability.
In light of the drawbacks of the prior-art encoder described above, it would be advantageous to devise an encoding apparatus which processes M symbols per cycle where M is greater than or equal to one, and/or further provides configurability for different values of M, and/or further provides configurability for different codes. The present invention provides such an encoding apparatus.
On the other hand, with an (n, k) cyclic code, a decoding operation first computes syndromes from the received codeword potentially containing errors. If all syndromes are zero, then the received codeword is a valid codeword and thus the decoding ends. If syndromes are not all zero, then the decoding operation proceeds to perform more steps to determine the locations and values of errors in the codeword. The present invention focuses on the first step of decoding, i.e. syndrome computation. Therefore, the terms decoding/decoder and syndrome computation/syndrome computer are used interchangeably in the present invention.
A widely known prior-art decoder based on the Homer's Algorithm is illustrated in FIG. 3. This decoder computes 2T syndromes by evaluating the received codeword polynomial r(X) at the 2T roots (305) of the generator polynomial of the code, respectively, where T is the maximum number of symbol errors correctable by the cyclic code. The syndromes [S0, . . . , S2T-1] are obtained and stored in the registers (303) after all received codeword symbols have been input via (301), one symbol per cycle. Since this decoder processes one symbol per cycle, it is to be clocked at the symbol transfer rate of the system which may be higher than the achievable or desirable clock rate of the decoder.
As a counterpart of the prior-art encoder, this prior-art decoder shares the same drawbacks of the prior-art encoder. Therefore, it would be advantageous to devise a decoder which processes M symbols per cycle, and/or further provides configurability for different values of M, and/or further provides configurability for different generator polynomials.
Since both the encoder and the decoder contain a significant amount of logic, such as Galois Field multipliers and Galois Field adders, it would be advantageous to merge the encoder and the decoder into a hybrid apparatus with the majority of the logic in the apparatus shared by the two functions.